|
|
1.
三角形的并行枚举算法
王卓, 索勃, 潘巍
计算机应用
2017, 37 (12):
3397-3400.
DOI: 10.11772/j.issn.1001-9081.2017.12.3397
经典GT算法是三角形并行枚举算法的MapReduce实现，然而该算法只能枚举全图的三角形结构，对部分顶点构成的三角形结构无法直接进行枚举。针对此问题，提出一种直接枚举部分顶点构成三角形结构的并行算法。首先，通过分析被选点的分布，给出被选点构成三角形的所有组合集合；然后，通过对该集合的筛选，实现对部分点构成三角形结构的直接枚举；最后，将该算法在Spark系统实现，以实现该算法的高效性和广泛性。在人工生成数据集和真实数据集上与GT算法进行对比实验，实验结果表明，所提改进算法的运行时间只有GT算法运行时间的1/3，在Spark上的运行时间仅是Hadoop上运行时间的1/7。该算法可用于更高效地直接生成图中任意点所构成的三角形数据集。
参考文献 |
相关文章 |
多维度评价
|
|
